codewriting

You're given a square matrix of integers matrix of size n × n.

Let's define a bouncing diagonal as a sequence which starts from a cell of the leftmost column, and continues diagonally (up-right) until it reaches the rightmost column, bouncing vertically if it reaches the top of the matrix.

demonstration

For each cell of the leftmost column, let's define its weight as the sum of the elements in the bouncing diagonals starting from that cell.

Your task is to sort the elements of the leftmost column by their weights in ascending order. In case of a tie, sort them by their values, also in ascending order.

Return the sorted values of the leftmost column of matrix as a single array.

Example

  • For

    matrix = [[2, 3, 2],
              [0, 2, 5],
              [1, 0, 1]]
    

    the output should be bouncingDiagonals(matrix) = [1, 2, 0].

    example 1

    • The weight of the first element is 2 + 2 + 1 = 5
    • The weight of the second element is 0 + 3 + 5 = 8
    • The weight of the third element is 1 + 2 + 2 = 5

    The second element weight is greater than the others, so its value (0) goes to the end of the resulting array. There's a tie between the first and third elements, so they must be sorted by their values (1, 2). Therefore, the final order of the elements in the leftmost column is [1, 2, 0].

  • For

    matrix = [[1, 3, 2, 5],
              [3, 2, 5, 0],
              [9, 0, 1, 3],
              [6, 1, 0, 8]]
    

    the output should be bouncingDiagonals(matrix) = [1, 9, 3, 6].

    example 2

    • The weight of the first element is 1 + 2 + 1 + 8 = 12
    • The weight of the second element is 3 + 3 + 5 + 3 = 14
    • The weight of the third element is 9 + 2 + 2 + 0 = 13
    • The weight of the fourth element is 6 + 0 + 5 + 5 = 16

    Each of the weights are different in this case, and their ascending order is first, third, second, and fourth. So the final order of the elements in the leftmost column is [1, 9, 3, 6].

Input/Output

  • [execution time limit] 3 seconds (java)

  • [input] array.array.integer matrix

    A matrix of integers.

    Guaranteed constraints:
    2 ≤ matrix.length ≤ 500,
    matrix[i].length = matrix.length,
    0 ≤ matrix[i][j] ≤ 1000.

  • [output] array.integer

    An array containing the values of the leftmost column of matrix, sorted by their weights.

[Java] Syntax Tips

// Prints help message to the console
// Returns a string
// 
// Globals declared here will cause a compilation error,
// declare variables inside the function instead!
String helloWorld(String name) {
    System.out.println("This prints to the console when you Run Tests");
    return "Hello, " + name;
}

main.java
Java
Tests
Custom Tests
Run tests
Test 1
Test 2
Test 3
Test 4
Test 5
Test 6
Test 7
Test 8
Test 9
Test 10
Test 11
Test 12
Test 13
Test 14
Test 15
Test 16

Formatting

Editor Mode
VS Code
Theme
Dark
Tab Size
Auto
Font Size
14px
Auto-brackets
Minimap
Code Completion
Error Highlighting

Hotkeys

CTRL/CMD + Enter
Submit
CTRL/CMD + R
Run
CTRL/CMD + S
Save
CTRL/CMD + Shift + >
Tab Right
CTRL/CMD + Shift + <
Tab Left